/*
 * @lc app=leetcode.cn id=51 lang=javascript
 *
 * [51] N 皇后
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  const put_queen = (k, i) => {
    for (let j = 0; j < n; j++) {
      // 所在列
      attack[j][i] = 1
      // 所在行
      attack[k][j] = 1
    }
    // 左斜
    let y = k
    let x = i
    while (y >= 0 && x >= 0) {
      attack[y--][x--] = 1
    }
    y = k
    x = i
    while (y < n && x < n) {
      attack[y++][x++] = 1
    }
    // 右斜
    y = k
    x = i
    while (y >= 0 && x < n) {
      attack[y--][x++] = 1
    }
    y = k
    x = i
    while (y < n && x >= 0) {
      attack[y++][x--] = 1
    }
  }
  const res = []
  let attack = Array.from({length: n}, () => Array.from({length: n}, () => 0))
  let queen = Array.from({length: n}, () => Array.from({length: n}, () => '.'))

  const backtrack = (k) => {
    if (k === n) {
      return res.push(queen.map((item) => item.join('')))
    }
    for (let i = 0; i < n; i++) {
      if (attack[k][i] === 0) {
        let temp = JSON.parse(JSON.stringify(attack))
        queen[k][i] = 'Q'
        put_queen(k,i)
        // 判断下一行是否有满足的皇后
        backtrack(k+1)
        // 回溯
        attack = temp
        queen[k][i] = '.'
      }
    }
  }
  backtrack(0)
  return res
};
// @lc code=end

